import java.lang.*;
import java.util.*;


public class Graph <GR> extends GraphABS <GR> {
    
         private int[] min_values;
         private Object[] reference;
         private boolean[] check_nodes;
         private GR inicio;
        
        /*Constructor*/
        public Graph() {
            super();
        }
        
// metodo para agregar un nuevo nodo
@Override      
        public void addNode(GR nuevonodo) {
            if (this.getMapa().contains(nuevonodo)) {
                System.out.println("YA EXISTE UN NODO SIMILAR");
            } else  {
                this.mapa_de_adyacencia.add(nuevonodo);
                this.lista_de_extremos.add(new LinkedList<Nodo<Integer>>());
            }
        }
// metodo para agregar una union - link
@Override   
        public void addLink(GR fuente, GR destino, Integer peso) {
            int temporal1 = this.getMapa().indexOf(fuente);
            Nodo<Integer> temporal2 = new Nodo<Integer>(destino.toString(), peso);
            
            if (this.mapa_de_adyacencia.contains(fuente) == false) {
                System.out.println("EL NODO NO EXSITE");
            } else if (this.mapa_de_adyacencia.contains(destino)) {
                this.lista_de_extremos.get(temporal1).add(temporal2);
            } else {
                System.out.println("EL NODO NO EXISTE");
            }
        }
// metodo para encontrar el camino mas corto
        public String shortestPath(GR inicio) {
            min_values = null;
            check_nodes = null;
            
            min_values = new int[this.mapa_de_adyacencia.size()];
            reference = new Object[this.mapa_de_adyacencia.size()];
            check_nodes = new boolean[this.mapa_de_adyacencia.size()];
            
            for(int i = 0; i < min_values.length; i++) {
                min_values[i] = 1000000;
                check_nodes[i] = false;
                reference[i] = null;
            }
            
            this.inicio = inicio;
            int pos_inicio = this.mapa_de_adyacencia.indexOf(this.inicio);
            min_values[pos_inicio] = 0;
            reference[pos_inicio] = this.mapa_de_adyacencia.get(pos_inicio);
            
            for(int i = 0; i < min_values.length; i++) {
                calcMinVal(pos_inicio);
                pos_inicio = nextSearch();
            }
            
            String res = "";
            
            res += "| ---------------------------------------------- \n";
            res += "| NODO ==> RUTA MÁS CORTA PARA LLEGAR ==> ORIGEN \n";
            res += "| ---------------------------------------------- \n";
            
            for(int i = 0; i < this.min_values.length; i++) {
                    if(min_values[i] == 1000000) {
                        res += "\n";
                        res += "| " + this.mapa_de_adyacencia.get(i) + " NO SE PUEDE LLEGAR";
                    } else {
                        res += "\n";
                        res += "| " + this.mapa_de_adyacencia.get(i) + " ==> " + this.min_values[i] + " ==> " + this.reference[i];
                    }
            }
            
            return res;
        }
        
// metodo que calcula el valor minimo
        public void calcMinVal(int pos_inicio) {
            LinkedList<Nodo<Integer>> list = this.lista_de_extremos.get(pos_inicio);
            this.check_nodes[pos_inicio] = true;
            
            for(int i = 0; i < list.size(); i++) {
                int pos = this.mapa_de_adyacencia.indexOf(list.get(i).getName());
                int val = list.get(i).getElement() + min_values[pos_inicio];
                
                if(val < this.min_values[pos]) {
                    min_values[pos] = val;
                    reference[pos] = this.mapa_de_adyacencia.get(pos_inicio);
                }
            }
        }
        // permite una nueva busqueda
        public int nextSearch() {
            int min = 1000000;
            int pos_min = 0;
            
            for(int i = 0; i < min_values.length; i++) {
                if (this.check_nodes[i] == false) {
                    if (this.min_values[i] < min) {
                        min = min_values[i];
                        pos_min = i;
                    }
                }
            }
            
            return pos_min;
        }
        // metodo que devuelve el camino mas corto en modo texto
        public String Floyd(GR ini) {
            return shortestPath(ini);
        }
       // metodo toString que devuelve la informacion en modo texto
        @Override
        public String toString() {
            String temp = "";
            for(int i = 0; i < this.mapa_de_adyacencia.size(); i++) {
                temp += "| " + i + " - " + this.mapa_de_adyacencia.get(i) + " ==> \t";
                
                for(int j = 0; j < this.lista_de_extremos.get(i).size(); j++) {
                    temp += this.lista_de_extremos.get(i).get(j) + " ";
                }
                temp += "\n";
            }
            return temp;
        }  
} 